#include <stdio.h>

void quickSort(int *array, int left, int right){
    //递归退出条件
    //如果当时查找对应的左边的位置，超过右边的位置，则标志查找结束了
    //直接结束当前方法
    if(left>right){
        return;
    }
    //设置中轴元素，默认取最左边的值
    int pivot = array[left];
    //分别设置i,j的位置
    int i = left;
    int j = right;

    //只要i和j没有重合-相遇，就一直查找
    while (i!=j)
    {
        //1.从右往左遍历查找比pivot小的元素
        //如果查找到比pivot小的元素，就停止
        //如果元素大于或等于pivot，则要继续，且不能越界遍历
        while(array[j]>=pivot&&j>1){
            //从右往左移动，以便下次继续寻找
            j--;
        }
        //2.从左往右遍历查找比pivot大的元素
        //如果查到比pivot大的元素，就停止
        //如果元素大于或等于pivot,则要继续，且不能越界遍历
        while(array[i]<=pivot&&i<j){
            i++;
        }

        //3.都停止后，互换i和j位置的元素
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    //while循环退出后，说明i和j相遇了
    //相遇后，互换pivot位置的元素和相遇位置的元素
    array[left] = array[i];
    array[i] = pivot;

    //位置互换后，中轴数就就位了
    //中轴pivot就位后，pivot左边的元素，都比他小
    //pivot右边的元素，都比他大
    //接下来在分别设置中轴左边元素的排序
    //i代表中轴pivot的位置，它左边的元素的位置，就是i-1
    quickSort(array,left,i-1);
    //设置中轴右边的顺序
    quickSort(array,i+1,right);
}

int main(){
    int arr[] = {3,0,1,8,7,2,5,4,9,6};
    int length = sizeof(arr)/sizeof(int);
    //初次调用，左边位置为0,右边位置为数组的最后一个元素
    quickSort(arr,0,length-1);
    for(int i = 0;i<length;++i){
        printf("%d ",arr[i]);
    }
    printf("\n");
    return 0;
}